N=100;
H=[-26380932,-22679357,-21366282,-13457591,-4887741,-441955,-629701,-48147959,-44988819,-37008287,-34553007,-32822530,-27440485,-26059840,-86550374,-80274487,-75151274,-66571940,-58312018,-57173400,-55555547,-111966819,-104762441,-104608922,-99638934,-94599754,-93271105,-87375061,-128943461,-125372919,-123410299,-120968152,-120929135,-117800008,-112442669,-156065934,-154165771,-150118917,-146319072,-138129923,-133682386,-128784580,-185451666,-182685268,-177544527,-177041658,-175084161,-170619454,-164167578,-191341425,0,5619921,12969090,13988019,20386542,20775622,23031319,29731499,30210691,37940743,38101204,37597555,41663154,46851680,49215536,48414077,51683125,52580132,59145190,64803261,69924361,69319336,70891891,75970471,80855020,87204420,90887962,98109753,102829029,110901208,118467298,124039154,124687803,124126019,128076565,128878805,129973370,129956203,132552256,131774312,134229618,133502905,140711479,144743353,151543993,153134235,153874703,154049876,162175525,166135681];
X0=153905588;
M=900;
S=[26,92,13,53,17,95,95,59,47,61,65,68,92,70,82,49,13,98,98,77,73,94,9,80,8,45,52,79,42,47,82,80,23,20,87,93,28,9,87,78,44,32,19,9,72,76,50,4,50,70,12,42,8,3,29,35,13,100,78,39,77,16,62,35,93,16,41,62,68,70,88,80,70,96,89,18,67,53,70,3,63,54,98,43,59,93,94,30,2,92,52,60,28,10,10,6,46,80,47,67,71,40,44,67,59,68,8,91,70,63,66,45,77,33,69,79,30,95,14,24,51,40,15,69,56,20,99,9,31,67,50,96,90,62,4,42,24,60,54,87,89,1,87,88,22,89,11,24,34,21,62,83,85,96,33,62,11,90,99,79,85,99,48,28,65,12,12,97,93,59,68,100,13,15,3,35,99,21,65,57,73,82,87,46,62,31,99,62,86,31,47,6,66,63,6,93,25,9,73,19,39,51,54,13,20,44,27,2,80,13,51,62,8,24,7,85,63,27,21,71,57,1,59,49,91,7,53,58,20,23,49,86,88,39,89,66,71,74,23,4,30,88,30,82,35,74,47,92,88,87,20,20,73,71,12,8,68,14,23,87,51,1,13,37,21,23,11,62,70,44,8,27,79,32,16,99,15,76,43,74,22,35,30,45,68,17,32,6,58,38,5,11,90,67,21,76,26,30,41,99,58,34,8,18,24,84,46,24,14,30,96,13,63,90,16,58,67,62,96,93,75,18,35,40,66,72,42,66,84,50,99,16,77,7,32,1,17,8,88,97,45,23,36,64,12,94,6,38,67,84,92,88,96,26,46,1,77,82,10,21,29,58,70,1,20,61,41,39,87,91,43,49,88,5,76,83,41,58,21,43,90,58,37,87,37,85,72,22,96,44,62,16,82,30,36,17,39,43,49,18,24,67,65,22,12,51,80,5,7,86,91,40,5,36,41,42,95,21,86,22,79,6,22,99,71,38,66,58,63,37,41,85,9,3,75,11,63,5,49,100,76,1,41,85,32,29,1,28,4,1,84,75,71,47,39,81,65,29,44,31,78,18,25,40,94,47,57,76,46,38,77,27,93,65,44,17,96,27,89,11,69,17,55,20,54,37,63,28,82,41,47,88,93,8,6,34,76,90,56,100,57,60,81,58,19,5,6,22,39,25,78,94,42,72,21,85,85,23,43,19,83,93,57,76,28,50,66,21,21,6,50,25,73,66,81,96,48,61,8,75,38,7,54,81,80,68,71,42,64,61,31,86,8,89,79,97,76,64,54,76,74,74,32,78,48,72,38,99,13,28,2,72,77,93,2,59,21,28,65,70,72,74,4,100,74,80,89,10,7,9,2,75,27,98,58,15,31,1,22,42,34,52,9,64,77,14,50,42,42,44,36,47,83,4,28,39,55,24,44,51,42,19,39,77,73,6,61,23,79,87,86,89,32,76,3,57,32,68,7,13,95,7,2,96,38,66,96,98,28,52,58,75,1,65,27,84,90,9,75,96,10,49,74,27,93,16,57,78,87,70,47,52,45,67,60,57,29,100,49,53,61,88,16,36,65,63,27,67,63,85,61,41,33,83,23,54,38,15,87,51,42,52,75,98,54,39,18,29,49,29,45,44,63,95,78,33,12,28,99,62,81,77,31,66,36,88,15,37,19,51,46,23,54,13,55,73,51,7,97,54,84,19,17,26,80,11,89,46,67,26,28,48,70,33,6,42,4,50,95,72,77,71,84,12,29,43,40,80,32,98,83,27,51,93,41,69,53,39,91,82,38,88,76,87,79,28,100,31,7,64,43,94,14,35,82,93,96,33,28,39,62,46,25,72,78,39,86,64,26,79,49,87,42,58,48,94,32,96,86,84,6,18,88,57,95,6,60,42,63,35,52,65,39,82,95,28,22,57,74,83,68,46,55,12,1,15,72,29,14,32,37,73,29,91,96,60,4,74,59,62,95,100,21,44,8,62,18,37,1,62,54,37,53,70,58,13,52,33,97,3,67,52,19,45,9,97,72,63,26,10,9,55,86,62,25,99,53,5,72,86];
X=[3798496,57499647,597012928,397299987,8418708,32492559,83304012,146235522,154695826,212419973,102132369,1000000000,13563208,864280791,13042767,232972313,108833349,4773236,83102640,145547645,31993110,642282698,22691007,1000000000,66607866,31984946,1455964,1000000000,61237399,24875638,49558174,161424694,221036725,16980069,129881969,1000000000,37832219,148746886,134011320,20220714,425079978,28242,265625493,85634106,230199855,169298333,29172418,234886983,170793810,107114335,102105847,63513423,92500517,1000000000,344334682,804300142,437395476,104760460,24729970,1000000000,130775280,218825778,37925842,10337395,538017618,500069871,412649704,116854374,233967536,338612168,273013364,38334259,157808605,247027477,995033645,77051558,97340412,115798434,146216403,324885334,50011535,196965920,83204907,7147650,59988240,79250206,1000000000,76611404,423654249,15853182,85989529,236340789,76370736,43746914,59392689,68192389,357571260,656228113,1000000000,57836718,680774152,228209030,145344534,18691849,854745995,1000000000,44562451,45745647,219788424,465565664,32333281,455521140,1000000000,121470980,191265426,18829238,24352953,105941371,96207415,67386078,237054206,330698500,133009129,270214961,29720554,34338390,188419380,84158510,117370286,171646558,47817406,167909665,26345843,312722829,321722622,165200390,137258643,186650056,115667476,492790370,954339965,238911538,231539697,4720978,85476505,318665744,287178892,544080693,21642788,2389917,1000000000,20630058,363397504,171562671,255087010,113610922,92728260,2409638,179150254,207226583,15570415,121563441,50274100,259941202,137365981,454097831,63478527,98438856,793344194,54705952,142222862,1000000000,1000000000,2149600,446561835,15823656,237750524,179435501,38745408,34911754,42244871,153363759,316546096,363207557,349134117,110136536,100427685,309552176,341349000,50329527,1000000000,3170281,1000000000,396609365,141127301,102935906,325411,78487381,225990590,824108450,16479261,145942651,259906014,231083024,10377080,876763882,71796459,232810505,371939769,267249261,1000000000,115223723,64579156,25874355,461807812,93208055,11194528,44684570,334871029,92491861,125084540,87318329,51737663,96075929,37693085,51922941,12095896,259350201,965928697,39533776,126992105,138770642,60756011,1934315,186007190,154836014,189056572,33816739,130665476,186181926,7366158,157854887,94151106,266585322,8122303,45738608,139922108,73954533,2983392,297582323,587180015,1000000000,285248445,470143145,4279371,101718039,82663274,269369309,216517760,55176067,22906847,197965226,239775857,2691358,258989090,289125,144274323,161632612,23795063,930246686,95701913,268049127,942681389,43829432,1000000000,464161738,24080380,5363249,83113216,104037417,164677083,70443549,185330521,69582496,191685486,10799744,25536036,53359469,31782449,305646668,1000000000,1000000000,40473664,87994360,47655680,167385238,49318608,952669125,722602566,1000000000,453419636,1000000000,335001847,1000000000,323217591,398087382,1000000000,365104541,83180997,110094025,664662425,382136554,65484681,121662990,54061740,96858114,150476607,1000000000,179714402,100061358,122782745,2885378,68094008,251005615,817004681,78741763,6999934,4062730,79522974,2697506,64738152,63775989,66787914,129943019,36526810,133776755,170859954,129894325,585062511,84460486,58899845,125308483,878114140,279681509,14494095,235720498,24865017,238774738,217887464,48511987,22332652,4891292,116042273,322323941,265272874,62000398,402879126,8795026,202893147,418196440,2832388,578189932,32699566,116370044,208762602,69449707,260717484,399533454,342251089,106942536,140055341,438170254,14093999,256696,209550531,1000000000,93329000,187612833,79972386,108694328,22801244,501660674,378069214,64781613,1000000000,15949488,185101066,44294390,180597454,878988258,19124777,276135041,450784556,25878279,59962454,576215428,45855054,65431076,71352148,27640374,462304588,69574146,276722083,98127346,104864891,147758069,271593894,93359914,9944700,5574270,157153130,113910351,34995026,81158315,224700180,1000000000,3000766,224694557,673433415,346203681,233609229,63581461,83204015,560290793,57475907,1000000000,46683977,813629975,701989177,88826578,8729891,314834413,46299636,100711547,189265764,5357917,275328162,233837999,122024687,373288575,115348206,161030618,1000000000,362859904,260980678,171868728,15272734,119063804,347463174,702395091,22141795,336697507,66282731,204692759,38463429,71377603,302834725,17231595,22749862,13432660,112428129,323975201,203425968,89174332,189286543,574346418,101227868,49850942,460621334,327313547,42741631,1000000000,70438978,95619555,145889194,109808951,12429210,59653482,1000000000,320421037,292552629,200698035,685188643,319495893,655599307,101825064,211337682,101259432,1817418,107856388,1000000000,13690710,451713821,146599956,15414334,65543017,3905448,405103173,134147423,48842612,140073533,1000000000,78624749,103149654,220121288,824728413,2796231,108400093,212477733,545832420,19930666,143926884,89912192,111568605,1657581,940063799,42900401,1000000000,27245830,4977722,198651632,861410462,16622571,184786478,1000000000,544815237,89416279,13703280,394486309,343213098,154360428,173946239,529202177,67386665,228679280,89086345,33692623,182616111,279696062,542048992,1237092,32534520,234617515,40823864,251470,188811180,169106757,34107493,12188047,1000000000,7348681,85305972,1068463,19454581,48627428,375976769,84626333,121795329,117618005,47420567,178740802,757083902,1000000000,31916215,446870449,22147963,22009045,220493157,1000000000,124463368,728495844,167784146,3833733,555830192,956841685,99917790,74551946,117155932,59469322,7661285,1000000000,278762232,12780558,241163158,13908167,301696576,275139495,716099687,642068715,1000000000,117449562,15509025,98136076,317933415,231449991,32904255,20275191,19056567,402998344,442155921,360214882,8079281,1000000000,1000000000,632786514,233926787,21455289,14700209,1166858,5956267,11389380,24580058,617415420,217678613,302601429,247882501,65669686,60512413,1000000000,31020409,1000000000,35064939,50288254,44055808,113475706,1061090,444017153,41433327,143930028,31799570,772650604,58032636,148105427,107498154,39293513,75187034,494027109,90879411,29756966,23561070,110546423,545285854,30467880,28364698,8680235,9718353,80703261,890941313,95155625,720694802,339562982,415108110,335634590,151704764,124270211,43896128,1497754,4004858,929574732,596126594,610160394,65823596,183269040,300605394,16124083,130491797,395526,96175223,201584777,10046979,133370071,512704502,62835584,1000000000,68335770,101446324,138431785,11254626,27217526,166533617,130537875,47363095,127812747,193878549,224588906,587563065,352000983,114179321,34648893,1000000000,15435014,92850296,178660532,128608637,32588366,734123825,20067422,18643054,173505644,54295058,240483812,86429418,16283232,1000000000,331986032,59684595,196831196,69459641,49093956,193118290,527704288,9936611,871772553,66649098,52848503,10619915,37095557,920326005,16757015,1000000000,521438623,42022333,159895766,189052140,17441385,457097847,27748960,45336202,42302704,129556072,133908850,154953256,205745077,1000000000,180630678,9199766,85442116,30743209,1000000000,290777925,37484957,965464567,1000000000,92969821,3149596,153837199,192552363,264392261,401709536,545943565,16906899,164002473,45490975,27165412,44670848,386512326,36198482,30718597,172909013,37327603,449270359,774624300,1705115,32969888,66613603,234688321,786464522,27879064,23177195,12636480,305057104,534399436,7591132,89254860,108947100,44595141,760089313,158638695,77314482,10486418,1000000000,230823682,228307723,242912167,9631472,150544586,167835810,1000000000,172726217,799092538,1000000000,74772740,183632290,1000000000,289473806,13317744,214169708,300936183,263838801,170110832,502461,725872838,517471699,30931053,223989315,56057887,125257516,35229362,1000000000,1000000000,109345834,857009025,26447229,1000000000,344178212,97794416,373501319,62576032,378623659,8814713,532526344,1000000000,1000000000,78685083,416608925,74354555,4950452,434083207,742781649,128425675,66141158,701941880,307044392,9096046,291262381,4417277,51795647,1000000000,113942798,37534389,162674681,12633716,77108326,10441859,204714712,80613498,74877412,49414546,850623775,41857565,74523817,14491091,78305050,98428669,102988351,187682976,363557418,798635,129859540,1000000000,33299478,17824033,1000000000,236063212,362715258,141447543,204130197,50691723,50543503,44044666,285781858,217873329,1449805,36975996,62414458,8341142,1000000000,181823557,17691959,452655404,33708980,278970514,1000000000,221096912,353359369,37162317,60832896,1000000000,271577895,98818503,1000000000,133562713,37043154,187488266,1000000000,1156531,367116481,328829018,432040418,291399055];